//排序加优先队列解决
struct com
{
    bool operator()(pair<int,int> &a,pair<int,int> &b)
    {
        return a.first>b.first;
    }
};
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& nums) {
        sort(nums.begin(),nums.end());
        priority_queue<pair<int,int>,vector<pair<int,int>>,com> q;
        q.push({nums[0][0],nums[0][1]});
        vector<vector<int>> ret;
        for(int i=1;i<nums.size();i++)//O(n)
        {
            auto x=q.top();
            //[[2,3],[2,2],[3,3],[1,3],[5,7],[2,2],[4,6]]
            //没有这个if最后输出的是[1,3][4,6][5,7]
            if(nums[i][0]>x.second)
            {
                q.pop();
                ret.push_back({x.first,x.second});
            }
            auto re=q.top();
            if(re.second>=nums[i][0])
            {
                if(re.second<nums[i][1])
                {
                    q.pop();
                    re.second=nums[i][1];
                    q.push({re.first,re.second});
                }
            }
            else q.push({nums[i][0],nums[i][1]});
        }
        while(!q.empty())
        {
            auto &[a,b]=q.top();
            q.pop();
            ret.push_back({a,b});
        }
        return ret;
    }
};
